package org.example.algo;

/**
 * 二分查找
 * 1. 在有序数组中查找某个数字
 * 2. 在有序数组中找到num最左位置
 * 3. 在有序数组中找到最右位置
 * @author shenguangyang
 */
public class N03_BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 10, 16, 16, 16, 20, 20, 26};
        System.out.println(binarySearch01(arr, 16));
        System.out.println(binarySearch02(arr, 16));
        System.out.println(binarySearch03(arr, 20));
    }

    public static int binarySearch01(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length;
        while (l <= r) {
            int midIndex = l + ((r - l) >> 1);
            if (arr[midIndex] == num) {
                return midIndex;
            } else if (arr[midIndex] < num){
                l = midIndex + 1;
            } else {
                r = r - midIndex;
            }
        }
        return -1;
    }

    public static int binarySearch02(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0;
        int r = arr.length;
        int tIndex = -1;
        while (l <= r) {
            int midIndex = l + ((r - l) >> 1);
            if (arr[midIndex] >= num) {
                r = midIndex - 1;
                tIndex = midIndex;
            } else {
                l = midIndex + 1;
            }
        }
        return tIndex;
    }

    /**
     * 在有序数组中找到最右位置
     * @return
     */
    public static int binarySearch03(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int l = 0, r = arr.length - 1;
        int ans = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] <= num) {
                ans = arr[mid] == num ? mid : ans;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
